定点算术单元II
AP SHANTHI博士
本模块的目标是讨论 Booth 的乘法技术、快速乘法技术和二进制除法技术。
布斯乘数
Andrew D. Booth 提出的 Booth 技术的主要优点是它可以处理正数和负数。它还可能具有减少操作次数的额外优势，具体取决于乘法器。下面给出其背后的原理。
考虑一个由 0 包围的 1 块组成的正乘数。例如，00111110。产品由以下给出：
M x 00111110 = M x (2 5 + 2 4 + 2 3 + 2 2 + 2 1 ) = M x 62，其中 M 是被乘数。通过重写与
M x 01000010 = M x (2 6 – 2 1 ) = M x 62
事实上，可以证明，一个二进制数中任何 1 的序列都可以分解为两个二进制数的差：
因此，我们实际上可以通过更简单的操作将乘法替换为原始数字中的一串1，添加乘数，将由此形成的部分乘积移到适当的位置，然后最后减去乘数。它利用了这样一个事实，即在二进制乘法器中处理 0 时，我们只需要进行移位就不需要做任何事情，并且类似于在乘以 99 时使用 99 = 100 − 1 的数学性质。
该方案可以扩展到乘法器中任意数量的 1 块（包括一个块中单个 1 的情况）。因此，
Booth 算法遵循此方案，在遇到块的第一个数字 (0 1) 时执行加法，并在遇到块的结尾 (1 0) 时执行减法。这也适用于负乘数。当乘法器中的那些被分组到长块中时，布斯算法 执行的加法和减法比普通乘法算法少。
作为现成的参考，请使用下表：
快速乘法
我们在上一节中看到了二进制乘法技术。本节将向您介绍两种加速乘法过程的方法。第一种方法是对 Booth 技术的进一步修改，有助于将 n 位操作数的加数数量减少到 n / 2。第二个技术减少了添加被加数所需的时间。
位 – 乘法器的对重新编码
这是从布斯算法推导出来的。它对乘法器位进行配对，并为每对提供一个乘法器位，从而将被加数的数量减少一半。这如下所示。
乘法只需要n /2
summands进位保存加法
进位保存加法器 (CSA) 可加快乘法过程中生成的被加数的加法。全加器的输入通常是两个数字的两位和前一级的进位输入。另一方面，在 CSA 的情况下，所有三个比特都是从三个数字中取出的。生成的进位被保存并添加到下一级。CSA 接受两个输入并输出两个输出。这如下所示。
如上图所示，每一位使用一个 CSA 块。该电路将 3 个 8 位数字添加为两个数字。
重要的一点是 c 和 s 可以独立计算，每个 ci 和 si 可以独立于所有其他 ci 和 si 计算。下面给出一个例子。
下面说明了使用 CSA 执行的乘法过程。
因此，为了加速乘法过程，乘法器的位对重新编码用于减少被加数。然后使用几个 CSA 步骤将这些被加数减少到 2。最终产品由使用 CLA 的加法运算生成。所有这三种技术都有助于减少乘法所需的时间。
二分法
二进制除法的示例如下所示。我们首先检查除数和被除数，决定只有当我们考虑被除数的前三位时，除数才会去，然后继续。尽管未显示，前两位必须为 0。然后我们得到商位 1，做减法，得到部分余数并做试减法（心理上）并相应地产生商位。重复这个过程，直到我们用完所有的被除数位。这如下图所示。
现在，机器实现也必须采用相同的逻辑。唯一的一点是，它必须系统地进行，并且要确定除数是否小于或等于被除数，我们必须进行试验比较/减法。基本上有两种类型的除法算法：
恢复师
非恢复分区
这两个都是正数。负数的处理方式相同，符号位分别处理。
恢复师
取被除数的第一位并进行试减。如果减法产生负的结果，我们产生一个商位为零，恢复，带来下一位被除数并继续。否则，我们只是继续使用商位 1。下面给出了算法、寄存器组织和示例。
其中N=分子，D=分母，n=#bits，P=部分余数，q(i)= 商的位 #i
非恢复分区
这是对恢复算法的修改。它结合了两个连续循环的恢复/不恢复和左移步骤，减少了操作次数。算法如下。
做第一次移位和减法
检查部分余数的符号
如果是负数，移位并添加
如果是正数，移位并减去
适当修正商位
如果最后的余数为负，则加上除数。
下面讨论一个例子。
余
总而言之，我们已经讨论了用于以相同方式处理正数和负数的 Booth 乘法技术。我们还讨论了进位保存加法，并了解了乘法的执行速度。最后，我们讨论了恢复和非恢复除法算法。
网页链接/支持材料
计算机组织，Carl Hamacher、Zvonko Vranesic 和 Safwat Zaky，第 5 版，McGraw-Hill 高等教育，2011 年。
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。